Search Results

Documents authored by Moss, Lawrence S.

Document
DOI: 10.4230/LIPIcs.CALCO.2023.14
Fractals from Regular Behaviours

Authors: Todd Schmid, Victoria Noquez, and Lawrence S. Moss

Published in: LIPIcs, Volume 270, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)

Abstract
We are interested in connections between the theory of fractal sets obtained as attractors of iterated function systems and process calculi. To this end, we reinterpret Milner’s expressions for processes as contraction operators on a complete metric space. When the space is, for example, the plane, the denotations of fixed point terms correspond to familiar fractal sets. We give a sound and complete axiomatization of fractal equivalence, the congruence on terms consisting of pairs that construct identical self-similar sets in all interpretations. We further make connections to labelled Markov chains and to invariant measures. In all of this work, we use important results from process calculi. For example, we use Rabinovich’s completeness theorem for trace equivalence in our own completeness theorem. In addition to our results, we also raise many questions related to both fractals and process calculi.
Cite as

Todd Schmid, Victoria Noquez, and Lawrence S. Moss. Fractals from Regular Behaviours. In 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 270, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{schmid_et_al:LIPIcs.CALCO.2023.14,
  author =	{Schmid, Todd and Noquez, Victoria and Moss, Lawrence S.},
  title =	{{Fractals from Regular Behaviours}},
  booktitle =	{10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-287-7},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{270},
  editor =	{Baldan, Paolo and de Paiva, Valeria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2023.14},
  URN =		{urn:nbn:de:0030-drops-188111},
  doi =		{10.4230/LIPIcs.CALCO.2023.14},
  annote =	{Keywords: fixed-point terms, labelled transition system, fractal, final coalgebra, equational logic, completeness}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2023.21
On Kripke, Vietoris and Hausdorff Polynomial Functors ((Co)algebraic pearls)

Authors: Jiří Adámek, Stefan Milius, and Lawrence S. Moss

Published in: LIPIcs, Volume 270, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)

Abstract
The Vietoris space of compact subsets of a given Hausdorff space yields an endofunctor V on the category of Hausdorff spaces. Vietoris polynomial endofunctors on that category are built from V, the identity and constant functors by forming products, coproducts and compositions. These functors are known to have terminal coalgebras and we deduce that they also have initial algebras. We present an analogous class of endofunctors on the category of extended metric spaces, using in lieu of V the Hausdorff functor ℋ. We prove that the ensuing Hausdorff polynomial functors have terminal coalgebras and initial algebras. Whereas the canonical constructions of terminal coalgebras for Vietoris polynomial functors takes ω steps, one needs ω + ω steps in general for Hausdorff ones. We also give a new proof that the closed set functor on metric spaces has no fixed points.
Cite as

Jiří Adámek, Stefan Milius, and Lawrence S. Moss. On Kripke, Vietoris and Hausdorff Polynomial Functors ((Co)algebraic pearls). In 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 270, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2023.21,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Milius, Stefan and Moss, Lawrence S.},
  title =	{{On Kripke, Vietoris and Hausdorff Polynomial Functors}},
  booktitle =	{10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-287-7},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{270},
  editor =	{Baldan, Paolo and de Paiva, Valeria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2023.21},
  URN =		{urn:nbn:de:0030-drops-188189},
  doi =		{10.4230/LIPIcs.CALCO.2023.21},
  annote =	{Keywords: Hausdorff functor, Vietoris functor, initial algebra, terminal coalgebra}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2021.5
Initial Algebras Without Iteration ((Co)algebraic pearls)

Authors: Jiří Adámek, Stefan Milius, and Lawrence S. Moss

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
The Initial Algebra Theorem by Trnková et al. states, under mild assumptions, that an endofunctor has an initial algebra provided it has a pre-fixed point. The proof crucially depends on transfinitely iterating the functor and in fact shows that, equivalently, the (transfinite) initial-algebra chain stops. We give a constructive proof of the Initial Algebra Theorem that avoids transfinite iteration of the functor. For a given pre-fixed point A of the functor, it uses Pataraia’s theorem to obtain the least fixed point of a monotone function on the partial order formed by all subobjects of A. Thanks to properties of recursive coalgebras, this least fixed point yields an initial algebra. We obtain new results on fixed points and initial algebras in categories enriched over directed-complete partial orders, again without iteration. Using transfinite iteration we equivalently obtain convergence of the initial-algebra chain as an equivalent condition, overall yielding a streamlined version of the original proof.
Cite as

Jiří Adámek, Stefan Milius, and Lawrence S. Moss. Initial Algebras Without Iteration ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CALCO.2021.5,
  author =	{Ad\'{a}mek, Ji\v{r}{\'\i} and Milius, Stefan and Moss, Lawrence S.},
  title =	{{Initial Algebras Without Iteration}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.5},
  URN =		{urn:nbn:de:0030-drops-153606},
  doi =		{10.4230/LIPIcs.CALCO.2021.5},
  annote =	{Keywords: Initial algebra, Pataraia’s theorem, recursive coalgebra, initial-algebra chain}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2017.23
Precongruences and Parametrized Coinduction for Logics for Behavioral Equivalence

Authors: David Sprunger and Lawrence S. Moss

Published in: LIPIcs, Volume 72, 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)

Abstract
We present a new proof system for equality of terms which present elements of the final coalgebra of a finitary set functor. This is most important when the functor is finitary, and we improve on logical systems which have already been proposed in several papers. Our contributions here are (1) a new logical rule which makes for proofs which are somewhat easier to find, and (2) a soundness/completeness theorem which works for all finitary functors, in particular removing a weak pullback preservation requirement that had been used previously. Our work is based on properties of precongruence relations and also on a new parametrized coinduction principle.
Cite as

David Sprunger and Lawrence S. Moss. Precongruences and Parametrized Coinduction for Logics for Behavioral Equivalence. In 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 72, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{sprunger_et_al:LIPIcs.CALCO.2017.23,
  author =	{Sprunger, David and Moss, Lawrence S.},
  title =	{{Precongruences and Parametrized Coinduction for Logics for Behavioral Equivalence}},
  booktitle =	{7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-033-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{72},
  editor =	{Bonchi, Filippo and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2017.23},
  URN =		{urn:nbn:de:0030-drops-80474},
  doi =		{10.4230/LIPIcs.CALCO.2017.23},
  annote =	{Keywords: precongruence, kernel bisimulation, finitary functor, coalgebra, behavioural equivalence}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.CALCO.2015
LIPIcs, Volume 35, CALCO'15, Complete Volume

Authors: Lawrence S. Moss and Pawel Sobocinski

Published in: LIPIcs, Volume 35, 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)

Abstract
LIPIcs, Volume 35, CALCO'15, Complete Volume
Cite as

6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Proceedings{moss_et_al:LIPIcs.CALCO.2015,
  title =	{{LIPIcs, Volume 35, CALCO'15, Complete Volume}},
  booktitle =	{6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-84-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{35},
  editor =	{Moss, Lawrence S. and Sobocinski, Pawel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2015},
  URN =		{urn:nbn:de:0030-drops-55622},
  doi =		{10.4230/LIPIcs.CALCO.2015},
  annote =	{Keywords: Theory of Computation, Logics and Meanings of Programs, Semantics of Programming Languages}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.CALCO.2015.i
Front Matter, Table of Contents, Preface, List of Authors

Authors: Lawrence S. Moss and Pawel Sobocinski

Published in: LIPIcs, Volume 35, 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)

Abstract
Front Matter, Table of Contents, Preface, List of Authors
Cite as

6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 35, pp. i-xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{moss_et_al:LIPIcs.CALCO.2015.i,
  author =	{Moss, Lawrence S. and Sobocinski, Pawel},
  title =	{{Front Matter, Table of Contents, Preface, List of Authors}},
  booktitle =	{6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)},
  pages =	{i--xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-84-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{35},
  editor =	{Moss, Lawrence S. and Sobocinski, Pawel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2015.i},
  URN =		{urn:nbn:de:0030-drops-55225},
  doi =		{10.4230/LIPIcs.CALCO.2015.i},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, List of Authors}
}
Document
DOI: 10.4230/LIPIcs.CSL.2011.5
Power-Set Functors and Saturated Trees

Authors: Jiri Adamek, Stefan Milius, Lawrence S. Moss, and Lurdes Sousa

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

Abstract
We combine ideas coming from several fields, including modal logic, coalgebra, and set theory. Modally saturated trees were introduced by K. Fine in 1975. We give a new purely combinatorial formulation of modally saturated trees, and we prove that they form the limit of the final omega-op-chain of the finite power-set functor Pf. From that, we derive an alternative proof of J. Worrell's description of the final coalgebra as the coalgebra of all strongly extensional, finitely branching trees. In the other direction, we represent the final coalgebra for Pf in terms of certain maximal consistent sets in the modal logic K. We also generalize Worrell's result to M-labeled trees for a commutative monoid M, yielding a final coalgebra for the corresponding functor Mf studied by H. P. Gumm and T. Schröder. We introduce the concept of an i-saturated tree for all ordinals i, and then prove that the i-th step in the final chain of the power set functor consists of all i-saturated trees. This leads to a new description of the final coalgebra for the restricted power-set functors Plambda (of subsets of cardinality smaller than lambda).
Cite as

Jiri Adamek, Stefan Milius, Lawrence S. Moss, and Lurdes Sousa. Power-Set Functors and Saturated Trees. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 5-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{adamek_et_al:LIPIcs.CSL.2011.5,
  author =	{Adamek, Jiri and Milius, Stefan and Moss, Lawrence S. and Sousa, Lurdes},
  title =	{{Power-Set Functors and Saturated  Trees}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{5--19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.5},
  URN =		{urn:nbn:de:0030-drops-32194},
  doi =		{10.4230/LIPIcs.CSL.2011.5},
  annote =	{Keywords: saturated tree, extensional tree, final coalgebra, power-set functor, modal logic}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact